/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 75. 颜色分类
 * <a href="https://leetcode.cn/problems/sort-colors/">...</a>
 * User: DELL
 * Date: 2023-07-20
 * Time: 23:27
 */
public class Solution {
    /**
     * 解题思路:
     * 本题可以通过遍历两次的方式,即第一次遍历将 0 全部调到 1 和 2 的前面
     * 第二次遍历,将 1 全部调到 2 的前面即完成,但是这样需要遍历两遍,因此
     * 可以改进方法.
     * 改进后的是通过两个下标,即 p0 记录的是 0 的下一个元素的下标, p1 记录
     * 的是 1 的下一个元素的下标.
     * 这样子遍历的时候,会出现以下情况
     * 1) nums[i] == 2 时: 不需要进行调整
     * 2) nums[i] == 1 时: swap(p1,i) && p1++ 即可
     * 3) nums[i] == 0 时: 需要进行如下分类讨论
     *      若 p1 == p0 时: swap(p0,i) && p1++ && p2++ 即可
     *      若 p1 != p0 时: 如果进行 swap(p0,i) ,会将 nums[p0] 位置的 1 和
     *          nums[i] 交换了位置,因此需要重新将这个 1 放到 p1 的位置
     *          即 swap(p0,i) && swap(p1,i) && p1++ && p2++ 即可
     * @param nums
     */
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                swap(nums,p0,i);
                if (p0 != p1) {
                    swap(nums,i,p1);
                }
                p0++;
                p1++;
            } else if (nums[i] == 1) {
                swap(nums,p1,i);
                p1++;
            }
        }
    }

    private void swap(int[] nums, int p1, int p2) {
        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }
}